The invention relates to the determination of the shapes and locations of complex objects based on range measurements from multiple sensors. More particularly, the invention relates to determining by trilateration the shapes and locations of multiple complex objects detected by multiple, spaced range sensors.
Trilateration is the art of determining the location of an object in space based on knowledge of the range (distance) of the object from multiple known locations. For instance, for simplicity, let us assume an idealized point object, i.e., an object that is infinitely small. Knowledge of the range of the object from a known location (e.g., one particular sensor) defines a sphere on which the object must lie, that sphere being the sphere that is centered at the sensor and has a radius equal to the measured range value. A range value from two separate locations (sensors) defines two distinct spheres on which the object must lie. Accordingly, the object must lie on the locus of points defined by the intersection of the two spheres, which is a circle. If the range from a third location (or sensor) to the object is known, then the object is known to lie on the locus of points defined by the intersection of all three spheres. For many practical scenarios, the intersection of these three spheres defines a single point which locates the object.
As another example, in a two dimensional environment (or at least an environment that can be assumed to be two dimensional), range readings from only two sensors to the same idealized point object will define two circles that overlap at two points. For many practical scenarios, however, only one of these intersections will be located in the detection areas of the sensors, thus locating the point object.
Of course, real world objects are not points, but are complex, having size and shape. Thus, real objects do not have a single well-defined location. Often, however, the measured range is the range to a point on the object. The particular point on the object that results in a reading at the sensor can depend on several factors, most particularly, the shape of the object and the orientation of the object with respect to the observing sensor. The particular point on an object that renders the range determined by the sensor often is the point on the object which presents a surface perpendicular to the beam propagation.
One example of a system that provides a range measurement, but no bearing measurement is a broad azimuth radar reflection system. As is well known in the related arts, one can send out a radio frequency (RF) beam from a known location and then receive reflections of that beam at the same known location and detect the time delay between the time the beam was issued and its reflection back to the sensor. Assuming that the detection point is approximately the same as the origination point of the beam, the delay period can be converted to a round-trip distance by multiplying it by the speed of the beam. The round trip distance can be divided by two to obtain the range to the object.
Of course, if the radar beam has a defined azimuth, the radar detection system also provides at least some bearing information. Air traffic radar is a well known example of a radar that provides both range and bearing information. Such radars send out very narrow azimuth beams from a rotating transmitter antenna. Therefore, range can be determined from the delay of the reflected beam, while at least some bearing information can be determined from the angular orientation of the antenna at the time of the receipt of the reflected beam.
In actuality, virtually all radar systems give some bearing information because the transmitters rarely generate totally spherical wave fronts with a full 360xc2x0 azimuth. For instance, even a radar with an azimuth as wide as 180xc2x0 eliminates half of the bearing spectrum (assuming one knows the direction in which the sensor is pointing).
In theory, when there is a single, point object in the field of view, trilateration is mathematically simple. However, real objects are not point objects. For instance, three sensors detecting the same object may detect slightly different surfaces of the object, wherein each surface is, essentially by definition, at a different location. Further, each sensor has some error range and thus each sensor reading will be inaccurate by some amount. Accordingly, in a real world situation, the three circles defined by the range readings of each sensor of a single object may not, in fact, intersect at a single point. Rather, there may be three closely spaced intersection points of two circles each, i.e., first and second circles, first and third circles, and second and third circles. Accordingly, various algorithms have been developed for estimating an exact location based on such readings.
In many real world uses of trilateration that assume a point object, if the objects are substantially farther away from the sensors than the sensors are from each other, the fact that each sensor might receive a reflection from a different point on the object is not problematic. However, when an object is close to the sensors, a point-object assumption can lead to significant errors in the determination of the location of an object or even the recognition that an object exists. For instance, FIG. 1A illustrates range measurements 13, 15 by two sensors 12, 14 to an ideal point object 16 located very close to the sensors in an environment that can be assumed to be two dimensional, while FIG. 1B illustrates range measurements by the same two sensors 12, 14 to an ideal line object 18 (commonly called a plate object) located very close to the sensors. If the detection algorithm assumes a point object, it can easily misinterpret the telemetry. For instance, the range circles 20, 22 from the two sensors 12, 14 do not intersect and thus an algorithm that assumes a point object would not detect the plate object 18.
On the other hand, if the algorithm that interpreted the range measurements assumed that the object was a plate object, it could accurately detect plate object 18, but would misinterpret the telemetry from the point object 16 in FIG. 1A as being a plate object represented by dashed line 24 in FIG. 1A.
If some information is known about the shape of an object in the field of view of a sensor array, it can be used to better determine the location or even the shape of the object. For example, if it is known that a sensor array is in an environment that can be assumed to be two dimensional and that consists entirely of plate objects, then the location and orientation of an object can be determined from only two sensor readings. Specifically, if the object can be assumed to be a plate, then the distance and orientation of the line is given by the line that is tangential to both range circles, as illustrated by line 18 in FIG. 1B. Assuming that the azimuth of the sensors is 180xc2x0 or less, as assumed in all Figures herein (and that they are pointing generally in the same direction and that direction is approximately perpendicular to a line drawn between the two sensors), there is likely only one line that will meet that criterion. Further, while the width of the plate object would not be known exactly, it would be known to be at least as wide as the distance between the two points 26 and 28 where the line is tangent to the two circles, respectively. This trilateration technique can be extended into three dimensions by adding a third sensor range reading.
Regardless of what assumptions can be made about the environment, matters can be become extremely complicated if there is potentially more than one object in the field of view of a sensor array. In many real world applications, there may be more than one object in the field of view such that each sensor receives a plurality of reflected wave fronts and, therefore, a plurality of range readings. Merely as an example, let us consider a highly simplified example in which four sensors each detect ten reflected wave fronts from the same ten actual objects. In this highly simplified example, as many as 10xc3x9710xc3x9710xc3x9710=10,000 xe2x80x9cpotential objectsxe2x80x9d can theoretically be identified by correlating the range circles from each sensor with the range circles of each other sensor. For example, let us assume that all objects are point objects. Then we can consider objects to potentially exist only where each of the four sensors has a range reading that defines a circle (or a sphere if a three dimensional system) that intersects at least one range circle from all three other sensors. It is likely that not all range readings (circles) of each sensor will intersect with the range readings of all three other sensors and, accordingly, with this assumption, it is likely that the number of potential objects will be substantially less than 10,000. However, the number of potential objects still could number in the hundreds in a realistic environment, even though there are only ten actual objects in the field of view.
Accordingly, an algorithm usually must be employed that attempts to pare down a large list of xe2x80x9cpotential objectsxe2x80x9d to an accurate smaller list of actual objects.
In sensor arrays that operate in environments with multiple objects in the field of view that can be of different shapes and that can be close to the sensor array, generating an accurate map of the environment can be extremely difficult.
Accordingly, it is an object of the present invention to provide an improved multi object location sensor method and apparatus.
It is another object of the present invention to provide a method and apparatus for determining the shape of objects using trilateration.
The invention is a method and apparatus for determining the shape and location of objects by trilateration based on the output of a plurality of range sensors. In accordance with the method and apparatus, the range measurements from a plurality of sensors are correlated with each other to identify one or more potential objects. With respect to each potential object, it is assumed that the object can be one of a finite number of possible predefined shapes. For each potential object, a metric is calculated for each of the predefined shapes using the set of range measurements upon which the potential object is based, the metric defining the likelihood that the readings correspond to an actual object of that predefined shape. Each potential object is then assumed to have the predefined shape that yielded the lowest metric (i.e., that yielded the metric that indicates the highest likelihood that the object has the corresponding shape).
In accordance with another aspect of the invention, once all of the potential objects in the field of the sensor array have been identified (and their shapes determined in accordance with the description above), the list of potential objects is pared down to a list of actual objects by ordering the list according by the calculated metrics (i.e., using the metric corresponding to the shape that the object was determined to have), with the potential object with the lowest metric at the top of the list and the potential object with the highest metric at the bottom of the list. The ordered list of potential objects is then pared down to a smaller list of actual objects by selecting the potential objects highest on the ordered list and assuming that it is an actual object and then removing from the list all other lower-ordered potential objects that are based on any of the individual measurements upon which the selected object is based. This process is then repeated for the next highest potential object remaining on the list until all potential objects on the list have either been selected as an actual object or removed from the list.